The invention lies in the general field of communication systems. It concerns in particular an external code which permits the correction of residual errors at the output of a turbodecoder, taking account of the constraints imposed by the use of a turbocode in general terms, and more particularly a turbocode based on an interleaver of the so-called xe2x80x9cx to xexe2x80x9d type.
It applies equally well to the coding of data representing a physical quantity, to the coding of data in the form of codes able to modulate a physical quantity, to the decoding of data-modulated signals as data, and to the decoding of data representing physical quantities. These data can, for example, represent images, sounds, computer data, electrical quantities or stored data.
The invention finds an application in the field of convolutional codes. When the latter are used to implement an iterative decoding, these codes are greatly improved when their coders contain a permutation device (xe2x80x9cinterleaverxe2x80x9d). In this case, they are normally referred to as xe2x80x9cturbocodesxe2x80x9d and the corresponding iterative decoder is referred to as a xe2x80x9cturbodecodexe2x80x9d. For convenience.
the operation performed by the turbocoder is referred to as a xe2x80x9cturbocodingxe2x80x9d and this operation supplies a so-called xe2x80x9cturbocodedxe2x80x9d sequence.
the operation performed by the turbodecoder is referred to as xe2x80x9cturbodecodingxe2x80x9d and this operation supplies a so-called xe2x80x9cturbodecodedxe2x80x9d sequence.
On these subjects, documents which serve as a reference are, on the one hand, the article by C. BERROU, A. GLAVIEUX and P. THITIMAJSHIMA entitled xe2x80x9cNear Shannon limit error-correcting coding and decoding:turbocodesxe2x80x9d published in the proceedings of the conference ICC""93. 1993, pages 1064 to 1070, and on the other hand the article by C. BERROU and A. GLAVIEUX entitled xe2x80x9cNear optimum error-correcting coding and decoding:turbo-codesxe2x80x9d published in IEEE Transactions on Communications, Volume 44, pages 1261 to 1271, in October 1996.
A parallel turbocoder (FIG. 1) with an efficiency equal to ⅓ can be considered as a pair of systematic recursive convolutional coders with divisor polynomials such that the first coder 120 produces a check sequence from the sequence of symbols to be coded a and the second coder 122 produced a check sequence of a sequence a* obtained by interlacing (or xe2x80x9cpermutationxe2x80x9d in an interleaver 121) of the sequence a.
In this context, the simultaneous return to zero of the two codes is a classic problem.
One way of resolving it has been found by one of the inventors and is summarised below.
For the purpose of clarity, it will be assumed hereinafter that the two divisor polynomials of the turbocoder are equal and termed g(x). Let m be the degree of the polynomial g(x) and let N0 be the smallest integer such that g(x) is a divisor of the polynomial 1+xNo.
For reasons described below, a polynomial g(x) is chosen where no divisor is the square of a polynomial of degree equal to or greater than 1, and this means that N0 is an odd number.
Let N be the size of the sequence a chosen so that it is an odd multiple of N0:N=Mxc2x7N0.
Any sequence of information symbols a for being turbocoded can then have a polynomial representation u(x) with binary coefficients of degree N-m-1. This sequence u(x) is precoded (or xe2x80x9cformattedxe2x80x9d) as:       a    ⁢          (      x      )        =            u      ⁢              (        x        )              +                  ∑                  i          =                      N            -            m                                    N          -          1                    ⁢              xe2x80x83            ⁢                        a          i                ⁢                  x          i                    
where the m binary symbols a1 are chosen so that a(x) is a multiple of g(x). As a consequence of this formatting (preceding) and the chosen values of the parameters, if a(x) is a multiple of g(x), then a*(x)=a(xc) modulo 1+xN is also a multiple of g(x) for any value of e which is a power of 2. It is necessary to consider that g(x) has no multiple factor since, in general, a*(x) has the guarantee of being divisible only by the irreducible factors of g(x).
In the remainder of the description, the type of permutations and interleavers disclosed above are referred to as xe2x80x9cx to xexe2x80x9d.
With general turbocodes, decoding is essentially an iterative procedure (see in this regard the document by C. BERROU and A. GLAVIEUX, xe2x80x9cNear optimum error-correcting and decoding:turbocodesxe2x80x9d, IEEE Trans. On Comm., Vol. COM-44, pages 1261-1271, October 1996).
Two prior-art documents have a few points of similarity with the problem to be resolved with regard to the correction of residual errors at the output of a turbodecoder.
A patent U.S. Pat. No. 4,276,646 of Texas Instruments describes a method and device for detecting and correcting errors in a set of data. In this patent a method is described consisting of putting the information in the form of subsets and adding to each subset a CRC (Cyclic Redundancy Check) so as to correct said subset.
An article by J. Andersen (xe2x80x9cTurbocoding for deep space applicationsxe2x80x9d, Proc. IEEE 1995 International Symposium on Information Theory, Whistler, Canada, September 1995) proposes the use of a BCH code for the correction of residual errors at the output of a turbodecoder.
These two documents present solutions which have a fairly limited effectiveness in the correction of residual errors, notably if they are applied to turbocodes of the type xe2x80x9cx to xexe2x80x9d. There are two main reasons for this:
The first reason relates to the fact that they do not take account of the structure of the residual errors. In fact a study of turbodecoders with an interleaver of the type xe2x80x9cx to xexe2x80x9d, by one of the inventors, revealed that the residual errors have a particular structure, provided that the iterations of the decoder are continued until their results stabilises.
The second reason is that the solutions proposed above supply coded sequences whose associated polynomial is not divisible by the divisor polynomial g(x) (their outputs are not formatted). A formatting function is therefore necessary before turbocoding.
The aim of the invention is therefore to remedy the aforementioned drawbacks in efficacy of residual error correction at the output of a turbodecoder.
To this end the invention proposes a method of transmitting binary data u by a sender to a receiver through a transmission channel, characterised in that said method includes a formatting function integrated in an external coding function for the binary data u.
This invention can be used in many telecommunication systems.
It applies in particular in cases where the sender uses a turbocoder with an xe2x80x9cx to xexe2x80x9d, interleaver, and the receiver uses a turbocoder with an xe2x80x9cx to xexe2x80x9d interleaver.
According to an even more particular embodiment, the binary data u are stored in an initial matrix U of L rows and K columns, L and K being predetermined, and an error correction code (N0, K) is allocated to each row, thus forming an intermediate matrix U1.
According to an even more particular embodiment, an error detection code (M, L) is allocated to each column of the intermediate matrix U1, thus forming a formatted matrix A, having M rows and N0 columns.
This arrangement makes it possible to detect the columns in error, on the principle of a product code.
According to a more particular embodiment, the error detection code (M, L) is produced by adding five additional bits calculated with the generator polynomial g1(y)=(1+y)(1+y+y4), where y=xNo, N0 being the number of columns in said formatted matrix A.
It will be understood that y is a binary variable evaluated along the columns of the matrix A.
The term (1+y) of the generator polynomial g1(y) ensures that the coding of the binary data u by the codes (N0, K) and (M, L) supplies a sequence which is divisible by the polynomial g(x). The term (1+y+y4) is an example of a polynomial used for error detection.
In a particular implementation, the error correction code (N0, K) has a minimum distance (d) greater than a predetermined number, representing the number of columns which can be corrected by the received matrix Axe2x80x2.
The invention also relates to a method of formatting binary data for a transmission method according to the invention, said formatting method being implemented by a central unit, using data (M, N0, L, K) previously stored in a non-volatile memory, and being characterised in that it includes the following steps.
receiving binary data u transmitted by a source,
storing data row by row in an initial matrix U of L rows and K columns,
coding each row of the initial matrix U with the code (N0, K), thus forming an intermediate matrix U1.
The formatting method then preferentially also includes the following steps:
coding each column of the intermediate matrix U1 with the code (M, L), thus forming a formatted matrix A, of size M x N0 
reading the matrix A row by row, and generating a sequence a, sent to the turbocoder.
The invention also relates to a method of decoding data received over a transmission channel, for a transmission method as disclosed above, said decoding method being implemented by a central unit, using data (M, N0, L, K, g, g1) previously stored in a non-volatile memory, and being characterised in that it uses a method of recovering data in whole columns.
The invention also relates to a method of decoding data received over a transmission channel, for a transmission method according to the above disclosure, said decoding method being implemented by a central unit, using data (M, N0, L, K) previously stored in a non-volatile memory, and being characterised in that it includes the following steps:
receiving binary data xc3xa3 supplied by a turbodecoder,
storing data row by row in a received matrix Axe2x80x2 of M rows and N0 columns,
decoding each column j of the received matrix Axe2x80x2 with the code (M, L), and erasing the column j if an error is detected, thus forming a received intermediate matrix U1xe2x80x2 of size L x N0.
The decoding method then preferentially also includes the following steps:
decoding each row i of the received intermediate matrix U1xe2x80x2 with the erasure decoder (N0, K), thus forming a received final matrix Uxe2x80x2 of size L x K,
reading the received final matrix Uxe2x80x2 row by row, and generating the sequence û, sent to a destination.
The invention relates in another aspect to a device for transmitting binary data u including a sender, a receiver, characterised in that said device has means adapted to effect, in an integrated fashion, a formatting function and a function of external coding of the binary data u.
According to a preferred arrangement, the sender has a turbocoder with an xe2x80x9cx to xexe2x80x9d interleaver, and the receiver has a turbocoder with an xe2x80x9cx to xexe2x80x9d interleaver.
According to a preferred embodiment, the device has means of storing the binary data u in a matrix of L rows and K columns, L and K being predetermined, and of allocating an error correction code (N0, K) to each row and an error detection code (M, L) to each column The invention also relates to a network, a computer, a video-camera, a facsimile machine, a photographic apparatus, a television receiver, a printer, a scanner and an audio/video player, characterised in that they have a device as succinctly disclosed above.
The invention also relates to:
an information storage means which can be read by a computer or microprocessor storing instructions of a computer program characterised in that it makes it possible to implement the method of the invention as succinctly disclosed above, and
an information storage means which is removable, partially or totally, and which can be read by a computer or microprocessor storing instructions of a computer program characterised in that it makes it possible to implement the method of the invention as succinctly disclosed above, and
an information storage means containing data resulting from the implementation of the method of the invention as briefly discussed above.
The advantages of this device, this network, this computer, this camera, this facsimile machine, this photographic apparatus, this television receiver, this printer, this scanner, this audio/video player and these storage means being the same as those of the method as succinctly disclosed above, they are not repeated here.